package leetcode.L1000;

import java.util.ArrayList;
import java.util.List;

public class EX842 {
    public static void main(String[] args) {
        String S = "123456579";
        
        List<Integer> res = new ArrayList<>();
        backtrack(S.toCharArray(),res,0);

        
    }
    public static boolean backtrack(char[] digit,List<Integer> res,int index){
        if (index == digit.length && res.size() >= 3) {
            return true;
        }

        for (int i = index; i <digit.length ; i++) {
            //如果当前位数是一位以上，第一位不能是零
            if(digit[index]=='0'&&i>index){
                break;
            }
            //截取并且数组化，i是截取末尾
            long num = subDigit(digit,index,i+1);
            if(num>Integer.MAX_VALUE){
                break;
            }
            int size = res.size();

            if(size>=2&&num>res.get(size-1)+res.get(size-2)){
                break;
            }
            if(size<=1||num==res.get(size-1)+res.get(size-2)){
                res.add((int)num);
                if(backtrack(digit,res,i+1)){
                    return true;
                }
                res.remove(res.size()-1);
            }

        }
        return false;
    }


    private static long subDigit(char[] digit, int start, int end) {
        long res = 0;
        for (int i = start; i < end; i++) {
            res = res * 10 + digit[i] - '0';
        }
        return res;
    }



}
